<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 回溯法的核心框架
      // for 选择 in 选择列表:
      // # 做选择
      // 将该选择从选择列表移除
      // 路径.add(选择)
      // backtrack(路径, 选择列表)
      // # 撤销选择
      // 路径.remove(选择)
      // 将该选择再加入选择列表
      var permute = function (nums) {
        // 方法一：回溯（）---时间O（）（不会算，至少是n!，要回溯递归）---空间：O（）（不会算，至少是n，递归栈的深度）
        let used = new Array(nums.length).fill(false);
        let track = [];
        let res = [];
        backtrack(nums, track, used);
        return res;

        function backtrack(nums, track, used) {
          // debugger;
          if (track.length === nums.length) {
            res.push([...track]);
            return;
          }
          for (let i = 0; i < nums.length; i++) {
            if (used[i]) {
              continue;
            }
            track.push(nums[i]);
            // 做选择
            // 将该选择从选择列表移除
            used[i] = true;
            backtrack(nums, track, used);
            // 撤销选择
            // 将该选择再加入选择列表
            track.pop();
            used[i] = false;
          }
        }
      };

      console.log(permute([1, 2, 3]));
    </script>
  </body>
</html>
